﻿//169. 多数元素
//给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n / 2 ⌋ 的元素。
//你可以假设数组是非空的，并且给定的数组总是存在多数元素。
//示例 1：
//输入：nums = [3, 2, 3]
//输出：3
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int left = 0, right = 0, n = nums.size();
        int firstwindowlen = -1, secondwindowlen = -1;
        // [1 0 1 2 1 3 1]
        int ret1 = 0;
        int ret2 = 0;
        while (right < n) {
            if (nums[right] == nums[left]) {
                if (firstwindowlen < right - left + 1) {
                    if (firstwindowlen != -1 && nums[left] != ret1) {
                        secondwindowlen = firstwindowlen;
                        ret2 = ret1;
                    }
                    firstwindowlen = right - left + 1;
                    ret1 = nums[left];
                }
                else if (right - left + 1 > secondwindowlen) {
                    secondwindowlen = right - left + 1;
                    ret2 = nums[left];
                }
            }
            else {
                left = right;
            }
            right++;
        }
        int count = 0;
        for (int i = 0; i < n; ++i) {
            if (nums[i] == ret1) {
                count++;
            }
        }
        if (count > n / 2) {
            return ret1;
        }
        return ret2;
    }
};



//842. 将数组拆分成斐波那契序列
//给定一个数字字符串 num，比如 "123456579"，我们可以将它分成「斐波那契式」的序列[123, 456, 579]。
//形式上，斐波那契式 序列是一个非负整数列表 f，且满足：
//0 <= f[i] < 231 ，（也就是说，每个整数都符合 32 位 有符号整数类型）f.length >= 3
//对于所有的0 <= i < f.length - 2，都有 f[i] + f[i + 1] = f[i + 2]
//另外，请注意，将字符串拆分成小块时，每个块的数字一定不要以零开头，除非这个块是数字 0 本身。
//返回从 num 拆分出来的任意一组斐波那契式的序列块，如果不能拆分则返回[]。
//示例 1：
//输入：num = "1101111"
//输出：[11, 0, 11, 11]
//解释：输出[110, 1, 111] 也可以。
// 131. 分割回文串 和 842. 将数组拆分成斐波那契序列使用了相同的回溯手法
// 回溯的时候函数头的设计中可以设计几个参数来记录上一层的某些状态信息
// 在这个题中，可以使用两个参数，prevnum 和 pretwonumsum这两个参数
// 传递给当前层，当前层怎么用？
// 当前层总要通过遍历pos之后的某个字符串能够形成pretwonumsum的情况
// 而prevnum 只是为了通过 makesum 和prevum相加之后传递给下一层的
class Solution {
public:
    vector<int> splitIntoFibonacci(string num) {
        int n = num.size();
        vector<int> ret;
        string maxn(to_string(INT_MAX));
        vector<int> curret;
        auto dfs = [&](auto&& dfs, int curpos, int pretwonumsum, int prevnum)->bool {
            if (curpos == n) {
                return curret.size() >= 3;
            }
            long long makesum = 0;
            for (int i = curpos; i < n; ++i) {
                if (i > curpos && num[curpos] == '0') {
                    break;
                }
                makesum = 10 * makesum + (num[i] - '0');
                if (makesum > INT_MAX) {
                    break;
                }
                if (curret.size() >= 2) {
                    if (makesum < pretwonumsum) {
                        continue;
                    }
                    else if (makesum > pretwonumsum) {
                        break;
                    }
                }
                curret.push_back(makesum);
                if (dfs(dfs, i + 1, makesum + prevnum, makesum)) {
                    return true;
                }
                curret.pop_back();
            }
            return false;
            };
        dfs(dfs, 0, 0, 0);
        return curret;
    }
};


//2400. 恰好移动 k 步到达某一位置的方法数目
//给你两个 正 整数 startPos 和 endPos 。
//最初，你站在 无限 数轴上位置 startPos 处。在一步移动中，你可以向左或者向右移动一个位置。
//给你一个正整数 k ，返回从 startPos 出发、恰好 移动 k 步并到达 endPos 的 不同 方法数目。
//由于答案可能会很大，返回对 109 + 7 取余 的结果。
//如果所执行移动的顺序不完全相同，则认为两种方法不同。
//注意：数轴包含负整数。
//示例 1：
//输入：startPos = 1, endPos = 2, k = 3
//输出：3
//解释：存在 3 种从 1 到 2 且恰好移动 3 步的方法：
//- 1 -> 2 -> 3 -> 2.
//- 1 -> 2 -> 1 -> 2.
//- 1 -> 0 -> 1 -> 2.
//可以证明不存在其他方法，所以返回 3
// 这个题又涉及到线性方程问题，也是问线性方程解的个数
// 这类问题能够使用的方法一般有两种：枚举和 数学方法
// 如果决定用枚举，就需要考虑不同的场景：
// 场景一：可以通过方程中的固定某个变量，快速的得到在固定之后方程解的个数
//     这一场景中一般是使用循环加枚举每一种情况讨论解的个数
// 场景二：可选方案是不确定的，不能总结出规律
//     这一场景中一般是使用直接枚举所有情况来确定解的个数
// 
// 如果决定使用数学方法，可以考虑的包括组合数，排列数等数学方法
// x + y = target

// class Solution {
//     #define MOD 1000000007
// public:
//     int numberOfWays(int startPos, int endPos, int k) {
//         int ret = 0;
//         vector<vector<int>> memo(2010, vector<int>(1010, -1));
//         auto dfs = [&](auto&& dfs, int curpos, int remainstep)->int{
//             if(abs(endPos - curpos) > remainstep){
//                 return 0;
//             }
//             if(remainstep == 0){
//                 return 1;
//             }
//             // curpos < 0 ->curpos + 1001
//             // curpos > 0 ->cupos
//             int& res = memo[(curpos < 0) * 1001 + curpos][remainstep];
//             if(res != -1){
//                 res = res % MOD;
//                 return res;
//             }

//             res = ((dfs(dfs, curpos + 1, remainstep - 1) % MOD) + (dfs(dfs, curpos - 1, remainstep - 1) % MOD) % MOD);
//             return res;
//         };
//         return dfs(dfs, startPos, k) % MOD;
//     }
// };

class Solution {
#define MOD 1000000007
public:
    int numberOfWays(int startPos, int endPos, int k) {
        // +1 +1 -1 -1
        // +1 -1 +1 -1
        // +1 -1 -1 +1
        // -1 +1 +1 -1
        // -1 +1 -1 +1
        // -1 -1 +1 +1
        if (abs(startPos - endPos) > k || (k - abs(endPos - startPos)) % 2 == 1) {
            return 0;
        }
        // 左方向要走(k - gap) / 2，右方向要走(k + gap) / 2
        // 那么就是从k步里选择a步来走正方向的组合数
        // c(k, a) = c(k - 1, a) + c(k - 1, a - 1)（最早的选或不选）
        int a = (k - (startPos - endPos)) / 2;
        vector<vector<int>> dp(k + 1, vector<int>(a + 1, 1));
        for (int j = 1; j <= a; ++j) {
            dp[0][j] = 0;
        }
        for (int i = 1; i <= k; ++i) {
            for (int j = 1; j <= a; ++j) {
                dp[i][j] = (dp[i - 1][j] % MOD + dp[i - 1][j - 1] % MOD) % MOD;
            }
        }
        return dp[k][a];
    }
};
